1. Field of the Invention
This invention relates to an error-correcting apparatus for correcting errors occurring in data which are coded using error-correcting codes, and particularly to an error-correcting apparatus for rapidly correcting errors occurring in reproduced or received digital signals in a compact disk player (hereinafter, referred to as"CD"), a digital audio player (hereinafter, referred to as "DAT"), a digital video signal record/reproduction apparatus (hereinafter, referred to as "digital VTR"), etc.
2. Description of the Related Art
In PCM (Pulse Code Modulation) recording and reproduction having typical examples such as a CD, DAT and digital VTR, an error correction using error-correcting codes is performed. Hereinafter, an error-correcting apparatus for performing an error correction will be described in which a Reed-Solomon code which is defined over a Galois field GF(q) is used as an error-correcting code actually used in a CD, DAT and digital VTR.
When multiple words are to be subjected to an error correction using a Reed-Solomon code, it is necessary to generate a syndrome from received data and obtain coefficients of an error position polynomial and error value polynomial. As examples of the method of obtaining coefficients of polynomials, known are the Euclidean algorithm, the Barlekamp's algorithm, etc. For example, the Euclidean algorithm is an algorithm of obtaining the greatest common polynomial of two given polynomials. That is, in the Euclidean algorithm, a division of polynomials using elements of a Galois field GF(q) as coefficients is performed to obtain an error position polynomial and error value polynomial. The Euclidean algorithm will be described in detail later.
Hereinafter, a description of a sequence of an error-correcting decoding of multiple words according to a Reed-Solomon code will be given. Generally, a Reed-Solomon code is decoded in the following sequence:
(1) A syndrome Si is obtained from received data (syndrome generation). PA0 (2) An error position polynomial .sigma. (z) and an error value polynomial .omega. (z) are obtained from the obtained syndrome Si (using the Euclidean algorithm, the Barlekamp's algorithm or the like). PA0 (3) An error position is obtained from the error position polynomial .sigma. (z) (chain search). PA0 (4) An error value is obtained from the error position and the error value polynomial .omega. (z). PA0 (5) An error of the received data is corrected on the basis of the error position and the error value (error correction).
Hereinafter, a method of decoding a Reed-Solomon code defined over a Galois field GF(2.sup.8) will be described.
When a received polynomial is represented by X(z) and a generator polynomial by G(z), a syndrome S is given by the following equation: ##EQU1## In the description of the prior art, the case where a Reed-Solomon code having a code length of n is decoded will be described.
Next, an error position polynomial .sigma. (z) and an error value polynomial .omega. (z) are obtained from the syndrome S (S(z)). Hereinafter, a method of calculating the error position polynomial and error value polynomial according to the Euclidean algorithm will be briefly described. The Euclidean algorithm consists of a repetition of divisions of polynomials defined over a Galois field, and can be expressed as follows. That is, in the Euclidean algorithm, divisions of two polynomials A(z) and B(z) defined over a Galois field, EQU A(z)/B(z)=Q.sub.0 (z) (quotient) . . . R.sub.c (z) (remainder) EQU B(z)/R.sub.0 (z)=Q.sub.1 (z) (quotient) . . . R.sub.1 (z) (remainder) EQU R.sub.0 (z)/R.sub.1 (z)=Q.sub.2 (z) (quotient) . . . R.sub.2 (z) (remainder )
are repeated until predetermined conditions are satisfied.
In an error-correcting code used in an optical disk, for example, a Reed-Solomon code having the minimum Hamming distance of 17 is employed, and therefore two polynomials are expressed as follows: ##EQU2## The divisions are repeated until the degree of the remainder polynomial is reduced to 7 or less. (In this example, the erasure is not considered.)
FIG. 1 is a flowchart of the process of obtaining solutions (error position polynomial and error value polynomial) of a basic equation according to the Euclidean algorithm. Initially, in step S1, each values are set to their respective initial values. The calculations illustrated in steps S2 and S3 are executed. If the judgment in step S4 is NO, the polynomials are set as illustrated in step S5, and the process returns to step S2. If the judgment in step S4 in YES, an error position polynomial .sigma. (z) and an error value polynomial .omega. (z) are obtained in step S6. In the figure, the symbol &lt; &gt; represents the Gauss' notation.
According to the Euclidean algorithm, therefore, an error position polynomial .sigma. (z) and an error value polynomial .omega. (z) can be obtained from a Reed-Solomon code having the minimum Hamming distance of 17, by performing divisions of polynomials over a Galois field eight times at the maximum.
An error position is obtained from the error position polynomial .sigma. (z) obtained according to the Euclidean algorithm. For this purpose, a method which is called a chain search is usually employed. In this method, powers .alpha..sup.i (i=0, 1, 2, . . . , n-1) of .alpha. (which is an element over a Galois field GF(2.sup.8)) are sequentially substituted in the error position polynomial .sigma. (z), thereby obtained the root .alpha..sup.i (corresponding to the error position) of .sigma. (z) in which .sigma. (.alpha..sup.i) is 0. In the above, n represents the code length.
According to this method, in order to calculate an error position, an n number of elements (.alpha..sup.0 to .alpha..sup.n-1) over GF (2.sup.8) corresponding to the code length are sequentially substituted in the error position polynomial .sigma. (z) to calculate .alpha..sup.i (corresponding to the error position) in which .sigma. (z)=0. Therefore, the step number of the calculation is n (code length).
Next, a prior art error-correcting apparatus will be described. FIG. 2 is a block diagram schematically showing the configuration of a prior art error-correcting apparatus for decoding a Reed-Solomon code. In the figure, 1 designates a RAM for storing data which are to be subjected to the error correction, 2 designates a syndrome generator for generating a syndrome from a received word, 3 designates an error-correcting arithmetic circuit for performing the error correction on the basis of a received syndrome from the syndrome generator 2, and 4 designates an error-correcting controller for controlling the entire the error-correcting apparatus.
FIG. 3 shows a specific circuit configuration of the syndrome generator 2. The reference numeral 10 designates registers for temporarily storing input data, 11 designates multipliers in which coefficients of the generator polynomial of a Reed-Solomon code are used as a multipliers, and 12 designates adders. The registers 10, the multipliers 11 and the adders 12 constitute the syndrome generator 2.
FIG. 4 shows a specific circuit configuration of the error-correcting arithmetic circuit 3. The reference numeral 20 designates a Euclidean arithmetic circuit for calculating an error position polynomial .sigma. (z) and an error value polynomial .omega. (z) in accordance with the Euclidean algorithm shown in FIG. 1, 21 designates a chain search circuit for calculating an error position from coefficient data of the error position polynomial .sigma. (z) output from the Euclidean arithmetic circuit 20, and 22 designates an error-correcting circuit for calculating an error value on the basis of coefficient data of the error value polynomial .omega. (z) output from the Euclidean arithmetic circuit 20 and error position data output from the chain search circuit 21, and for performing an error correction. The Euclidean arithmetic circuit 20, the chain search circuit 21 and the error-correcting circuit 22 constitute the error-correcting arithmetic circuit 3.
FIG. 5 is a block diagram of a divider section of the Euclidean arithmetic circuit 20 which performs a division on the polynomials over a Galois field. In the figure, 50 and 51 designate input terminals, 52a and 52b designate registers for storing coefficient data of divisor and dividend polynomials, 53 designates selectors, 54 designates multipliers, and 55 designates adders. The registers 52a and 52b, the selectors 53, the multipliers 54 and the adders 55 constitute the divider section for a division of the polynomials over a Galois field in the Euclidean arithmetic circuit 20.
FIG. 6 shows a specific circuit configuration of the chain search circuit 21. The reference numeral 31 designates feedback registers to which setting coefficient data of the error position polynomial .sigma. (z) are set at the start of a chin search, and thereafter outputs of sequential multipliers 32 are sequentially set, 32 designates multipliers, 33 designates an adder, 34 designates a judging circuit for judging whether the output of the adder 33 is 0 or not, 35 designates a coefficient counter for counting the number of feedback operations performed by the feedback registers 31, and 36 designates a register for storing the contents of the coefficient counter 35 in response to the 0-judgment output from the judging circuit 34. The feedback registers 31, the multipliers 32, the adder 33, the judging circuit 34, the coefficient counter 35 and the register 36 constitute the chain search circuit 21.
With reference to FIGS. 2 to 6, the operation of the error-correcting apparatus will be described. When an error correction is started, received or reproduced data which are stored in the RAM 1 and include errors occurring during the receiving or reproduction process are read out from the RAM 1 in order to generate a syndrome in the syndrome generator 2. In the syndrome generator 2, the data read out from the RAM 1 (in the form of a received polynomial) is divided by a generator polynomial to generate a syndrome. The address from which the received data are read out and the reading control signal are supplied from the error-correcting controller 4.
The syndrome generator 2 having the circuit configuration shown in FIG. 3 consists of the registers 10 arranged in the form of a shift register, the multipliers 11 in which input data (feedback data) are multiplied by coefficient data corresponding to the terms of the generator polynomial, and the adders 12. In the syndrome generator 2, input data are shifted while sequentially calculating them in the arithmetic circuits, thereby executing the division of polynomials over a Galois field. Accordingly, the execution of the arithmetic requires steps the number of which corresponds to the code length (i.e., n steps). The detail of the syndrome generator 2 is described by "Code Theory" pp. 115-118, written by Hideki Imai, published by electronic data transmission society.
The syndrome generated by the syndrome generator 2 in the manner described above is output together with a syndrome generation end signal to the error-correcting arithmetic circuit 3 and the error-correcting controller 4. The error-correcting controller 4 generates a Euclidean arithmetic start signal in response to the syndrome generation end signal, and supplies it to the error-correcting arithmetic circuit 3. In the error-correcting arithmetic circuit 3 which receives the Euclidean arithmetic start signal, the Euclidean arithmetic circuit 20 calculates an error position polynomial .sigma. (z) and an error value polynomial .omega. (z) on the basis of the syndrome output from the syndrome generator 2.
Next, the operation of the divider section of the Euclidean arithmetic circuit 20 which is shown in FIG. 5 will be described. When a syndrome generation end signal is input, the registers 52 are set to the respective initial values. More specifically, Z.sup.2t is set in the upper registers 52a, and the coefficients of the syndrome polynomial calculated by the syndrome generator 2 are set in the lower registers 52b. While shifting the data of the dividend side (initially, the upper registers 52a in which the data of Z.sup.2t are set), divisions of polynomials over a Galois field are executed. The divisions are repeated until the degree of the polynomial of the dividend side is reduced to a value less than that of the polynomial of the divisor side. In FIG. 5, the divider section is so configured that the selectors 53 connected to the registers 52 of the dividend side select the outputs of the respective adders 55, and that the selectors 53 connected to the registers 52 of the divisor side select the outputs of the respective registers 52. As a result, the data in the registers 52 of the dividend side are shifted and a division is executed.
As a result of the division, the registers of the dividend side store the remainder of this division. Thereafter, a further division is performed while setting the polynomial stored in the divisor registers as the dividend, and the remainder of this division as the divisor. This exchange of the dividend and the divisor is done by switching the outputs of the selectors 53. This operation is repeated until the termination conditions shown in FIG. 1 are satisfied. When the conditions are satisfied, the Euclidean arithmetic circuit 20 calculates coefficient data of the error position polynomial and error value polynomial, and outputs the calculated coefficient data together with a Euclidean arithmetic end signal to the chain search circuit 21 and the error-correcting controller 4. The divider section of the Euclidean arithmetic circuit 20 is described in Japanese Patent Application Laid-Open No. HEI1-276,825 (1989).
The error-correcting controller 4 outputs a chain search start signal for starting the operation of the chain search circuit 21, in response to the Euclidean arithmetic end signal from the Euclidean arithmetic circuit 20. Upon receiving the chain search start signal, the chain search circuit 21 calculates the error position on the basis of the coefficient data of the error position polynomial .sigma. (z) calculated by the Euclidean arithmetic circuit 20. Referring to FIG. 6, the operation of the chain search circuit 21 will be specifically described. In the chain search circuit 21, when the cain search start signal is input, the coefficient counter 35 is set to 0, and the feedback registers 31 are respectively set to the coefficient data of the error position polynomial .sigma. (z) calculated by the Euclidean arithmetic circuit 20. The outputs of the feedback registers 31 are respectively multiplied by the multipliers which are previously set in the multipliers 32, and then latched again in the feedback registers 31.
In the adder 33, the outputs of the feedback registers 31 are added with each other. The judging circuit 34 checks the result of this addition to judge whether it is 0 is not. If the result is 0, the value of the coefficient counter 35 is written into the register 36 (this counter value corresponds to the error position). For the completion of the chain search, n steps are required. The chain search circuit 21 is described in detail in the above-mentioned "Code Theory" pp. 165-166.
In the error-correcting circuit 22, on the basis of the error position data from the chain search circuit 21, erroneous data stored in the RAM 1 are at first read out. At the same time, the error-correcting circuit 22 obtains error values on the basis of the error value polynomial .omega. (z) from the Euclidean arithmetic circuit 20 and the error position data from the chain search circuit 21. The erroneous data read out from the RAM 1 are added with the above-mentioned error values to be subjected to an error correction. The data which have been subjected to an error correction are replaced with the erroneous data in the RAM 1. Hereinafter, data which has been subjected to an error correction is referred to as "error-corrected data".
FIG. 7 shows a simple flow of encoding and decoding processes in the error-correcting apparatus which is applied to a digital VTR. In FIG. 7, data which have been input to the error-correcting apparatus are divided into a plurality of unit data blocks. Generally, error-correcting codes are double-encoded. In this case, plural one of the unit data blocks are arranged two-dimensionally as shown in FIG. 8. To the arranged blocks, an error-correcting encoder adds error-correcting codes in the vertical direction (C2 codes), and then error-correcting codes in the recording direction (C1 codes). The code configuration shown in FIG. 8 is described in "AN EXPERIMENTAL HOME-USE VCR WITH THREE DIMENSIONAL DCT AND SUPERIMPOSED CORRECTION CODING", IEEE TRANSACTIONS ON CONSUMER ELECTRONICS, August 1991, Vol. 37, No. 3, as an example of an error-correcting code which is used in a home-use digital VTR. FIG. 9 shows a code configuration of one line in the recording direction shown in FIG. 8. In a digital VTR, data added with error-correcting codes are recorded on a recording medium, or, in a communication unit, transmitted to a communication channel. Data reproduced from the recording medium are subjected to an error-correcting process in order to correct errors which occurred in the reproduction process. In the error-correcting process, errors included in the reproduced data are corrected or detected. The error-corrected data are sent to the process of the next step.
Next, the signal process timing of each portion of the prior art error-correcting apparatus in which the data of one line shown in FIG. 9 are to be decoded will be described with reference to a timing chart shown in FIG. 10. FIG. 10 illustrates various control signals output from the error-correcting controller 4 (a syndrome generation start signal, the Euclidean arithmetic start signal, the chain search start signal, and an error correction start signal), operation timings of the circuits (the syndrome generation timing of the syndrome generator 2, the arithmetic timing of the Euclidean arithmetic circuit 20, the arithmetic timing of the chain search circuit 21, and the error correction timing of the error-correcting circuit 22), and the data access state of the RAM 1. When an error correction is started, the error-correcting controller 4 outputs the syndrome generation start signal to the syndrome generator 2, and generates addresses of the RAM 1 from which reproduced data including errors caused in the reproduction process are to be read out, and also control signals. Upon receiving the syndrome generation start signal, the syndrome generator 2 sets the values of the registers 10 to 0, and performs a predetermined arithmetic (division) process on the data read out from the RAM 1. As described above, in the syndrome generation, the number of steps required for the completion of the arithmetic corresponds to the code length, or 241 are required. This arithmetic time is indicated by portions labeled SY in FIG. 10.
After the syndrome generation is ended, the syndrome generator 2 outputs the syndrome generation end signal. In response to the syndrome generation end signal, the error-correcting controller 4 outputs the Euclidean arithmetic start signal. The Euclidean arithmetic circuit 20 which receives the Euclidean arithmetic start signal performs the division of the polynomials over a Galois field GF(2.sup.8) in the manner described above, and calculates an error position polynomial .sigma. (z) and an error value polynomial .omega. (z). When a Reed-Solomon code having the minimum distance of 17 used in this prior art example is to be decoded using the Euclidean algorithm (or the error position polynomial .sigma. (z) and error value polynomial .omega. (z) are to be calculated), the calculation can be completed by repeating the division of the polynomials eight times at the maximum. This arithmetic time is indicated by portions labeled EU in FIG. 10. The number of steps required in this process varies depending on the whole circuit configuration or the Euclidean arithmetic circuit 20. The process of calculating the error position polynomial .sigma. (z) and error value polynomial .omega. (z) from the Reed-Solomon code having the minimum distance of 17 shown in FIG. 9 with using the Euclidean algorithm can be realized by about 120 steps. The detailed description of the operation of the circuit is omitted. The decoding time in the Euclidean arithmetic circuit 20 requires about 120 steps in order to perform the operation including: the division operations in the divider; the operation of setting data; the generation of the control signals; the calculation of the error position polynomial .sigma. (z) and error value polynomial .omega. (z); and the calculation of a modified syndrome in the case that an erasure is done (this operation is omitted in this example).
When the Euclidean arithmetic is ended, the Euclidean arithmetic circuit 20 outputs the Euclidean arithmetic end signal. In response to the Euclidean arithmetic end signal, the error-correcting controller 4 outputs the chain search start signal. In the chain search circuit 21 which receives the chain search start signal, the coefficient counter 35 is set to 0, and the feedback registers 31 are respectively sets to the coefficient data of the error position polynomial .sigma. (z) calculated by the Euclidean arithmetic circuit 20. The outputs of the feedback registers 31 are respectively multiplied by the multipliers which are previously set in the multipliers 32, and then latched again in the feedback registers 31. The coefficient counter 35 counts the number of feedback operations performed by the feedback registers 31. In the adder 33, the outputs of the feedback registers 31 are added with each other. The judging circuit 34 checks the result of this addition to judge whether it is 0 or not. If the result is 0, the value of the coefficient counter 35 is written into the register 36. As described above, in the chain search circuit 21, the maximum number of steps required for the calculation of an error position corresponds to the code length, or 241 steps. This arithmetic time is indicated by portions labeled CH in FIG. 10.
When the chain search is ended, the chain search circuit 21 outputs a chain search end signal. In response to the chain search end signal, the error-correcting controller 4 outputs the error correction start signal. A detailed timing chart of the error-correcting circuit 22 is shown in FIG. 11. Upon receiving the error correction start signal, the error-correcting circuit 22 calculates an error value, using the error value polynomial .omega. (z) and the error position data from the chain search circuit 21. On the other hand, the error-correcting controller 4 reads out erroneous data from the RAM 1 on the basis of the error position data. The erroneous data read out from the RAM 1 is added with the error value at the timing of the next clock pulse, to be subjected to the error correction. The error-corrected data is written again into the RAM 1 at the next clock pulse. Therefore, the process of executing the error correction of one symbol in the error-correcting circuit 22 requires a period of at least 3 clock pulses, resulting in error correction of eight symbols which requires at least 24 steps.
An error-correcting apparatus is an essential apparatus for a process of correcting errors occurring in signals reproduced in a CD, DAT or digital VTR or in a transmitted signal, However, a prior art error-correcting apparatus has the following problems. One of the problems is that the decoding time required for performing an error correction on one line in a prior art error-correcting apparatus is very long as shown in FIG. 10. In the prior art example, although circuit architecture for a high speed arithmetic is employed in the divider section of the Euclidean arithmetic circuit 20, the process of decoding the C1 block of one line shown in FIG. 9 requires the decoding time of 626 steps (241+120+241+24=626). Several kinds of circuit architecture for increasing the operation speed of the Euclidean arithmetic circuit 20 shown in FIG. 5 are disclosed in several Japanese Patent Applications. Even when the arithmetic time of the Euclidean arithmetic circuit 20 is shortened, however, the process times of the syndrome generation, the chain search, etc. cannot be shortened, with the result that the required process time may not be maintained in an apparatus such as a digital VTR which needs a real time and high speed signal processing.
A circuit configuration for increasing the operation speed of an error-correcting apparatus is proposed in Japanese Patent Application Laid-Open No. HEI3-63,973 (1991). In this configuration, the syndrome generator 2 and error-correcting arithmetic circuit 3 shown in FIG. 4 are operated in parallel. Referring to a timing chart of FIG. 12, the operation of the proposed error-correcting apparatus will be described. Upon receiving a parallel operation start signal, the syndrome generator 2 starts the syndrome generation. At the same time, the Euclidean arithmetic circuit 20 of the error-correcting arithmetic circuit 3 calculates in the above-mentioned manner the error position polynomial .sigma. (z) and an error value polynomial .omega. (z), according to the Euclidean algorithm. When the arithmetic in the Euclidean arithmetic circuit 20 is completed, the chain search circuit 21 calculates an error position on the basis of the coefficient data of the error position polynomial. After the calculation of the error position in the chain search circuit 21, the error-correcting circuit 22 performs the error correction. The syndrome generator 2, the Euclidean arithmetic circuit 20, the chain search circuit 21 and the error-correcting circuit 22 operate in the same manner as the above-described prior art example, and therefore the detailed description of their operation is omitted. The number of arithmetic steps in each of the circuits is shown in FIG. 12. FIG. 12 shows also the timings of various control signals output from the error-correcting controller 4 in the same manner as those in the above-mentioned prior art example, the operation timing of each circuit, and the data access state of the RAM 1. The parallel operation of the syndrome generator 2 and the error-correcting arithmetic circuit 3 reduces the minimum number of steps required for performing the error correction on the C1 block of one line shown in FIG. 9, to 385 steps.
Also in this prior art example, however, when a Reed-Solomon code having the form of a product code such as shown in FIG. 8 is to be decoded, the error correction according to C2 codes is performed after the completion of the error correction according to C1 codes. This requires a large number of decoding steps, resulting in that the decoding process cannot be conducted in real time. Furthermore, since the C2 decoding is performed on data which have been subjected to the C1 decoding, data must be read out again from the same RAM. As a result, a countermeasure such as that error-correcting apparatus are connected in parallel to perform a concurrent processing must be taken, thereby arising problems such as that the circuit scale is enlarged.
As shown in FIGS. 3 and 6, in the syndrome generator 2 and the chain search circuit 21, the outputs of the registers are connected in series or parallel with the multipliers and adders in which the outputs are multiplied or added by a constant over a Galois field. From the view point of hardware, this means that signals must pass through four stages of EX-OR gates at the maximum. By contrast, in the Euclidean arithmetic circuit 20, signals must pass through about seven stages of EX-OR gates and several selectors (these stage numbers may vary depending on the hardware configuration), thereby arising another problem in that it is difficult to increase the operation speed of the Euclidean arithmetic circuit 20 as compared with the syndrome generator 2 and the chain search circuit 21. There is a further problem in that the circuit scale of the Euclidean arithmetic circuit 20 is larger than that needed. Furthermore, the error correction of one symbol in the error-correcting circuit 22 requires at least 3 steps, thereby causing a problem in acceleration of the operation speed.
Recently, various companies are developing a digital VTR, and therefore the subject of increasing the operation speed of an error-correcting apparatus becomes important. FIG. 13 is a block diagram of a prior art divider section (hereinafter, referred to as "core circuit") for polynomials defined over a Galois field in the Euclidean arithmetic. The core circuit is disclosed in Japanese Patent Application Laid-Open No. HEI3-172,027 (1991). In the following description, it is assumed that the adders, multipliers and dividers described below are those for respectively executing the addition, multiplication and division operations over a Galois field.
In the figure, 81a and 81b designate registers for storing coefficient data of a dividend polynomial and a divisor polynomial, 82 and 83 designate selectors which select either of the outputs of the registers 81a and 81b, 84 designates a divider, 85 designates multipliers, 86 designates adders, 95 designates an input terminal, and 87 and 88 designate degree detection circuits for detecting the degrees of polynomials stored in the registers 81a and 81b. The reference numeral 89 designates a Euclidean arithmetic controller which controls the entire operation. More specifically, the controller 89 controls the selectors 82 and 83, judges the termination conditions of the Euclidean algorithm on the basis of degree judgments output from the degree detection circuits 87 and 88, and performs other operations. The registers 81a and 81b, the selectors 82 and 83, the divider 84, the multipliers 85, the adders 86, the degree detection circuits 87 and 88, and the Euclidean arithmetic controller 89 constitute the divider section (core circuit) for polynomials defined over a Galois field in the Euclidean arithmetic circuit. This prior art example is so configured that registers closer to the right end store the highest-degree coefficient of polynomials.
Next, the operation principle of the divider which has the above-mentioned configuration and executes a division will be briefly described. A dividend polynomial and a divisor polynomial are expressed as follows: ##EQU3## wherein n&gt;m. A longhand calculation procedure of the division is shown in Eq. 1 below. ##EQU4##
As shown in Eq. 1, the calculation is repeated until the degree of the remainder of the dividend polynomial becomes smaller than the degree of the divisor polynomial. In Eq. 1, the coefficient data of the last remainder polynomial are represented by Ci (i=0, 1, 2, . . . , m-1).
In the Euclidean algorithm shown in FIG. 1, when the degree of the remainder polynomial: EQU R(Z)=C.sub.m-1 +C.sub.m-2 Z.sup.m-2 + . . . +C.sub.1 Z+C.sub.0
fails to satisfy the predetermined conditions, the division is repeated while setting the divisor polynomial M2(z) as the dividend polynomial, and the remainder polynomial R(Z) as the divisor polynomial. In the divider of FIG. 13, the exchange of the divisor polynomial and the dividend polynomial is conducted by switching the selectors 82 and 83.
Similarly, Eq. 2 shows the calculation procedure of dividing M2(Z) by R(Z). ##EQU5##
In this longhand calculation, for the sake of convenience, it is assumed that the highest degree C.sub.m-1 of the remainder polynomial R(Z) is not 0. (When the highest degree is 0, generally, the degree detection circuits 87 and 88 shown in FIG. 13 judge the degrees of the dividend polynomial and divisor polynomial, the coefficient data of the dividend polynomial and divisor polynomial are shifted until the highest degrees of the dividend polynomial and the divisor polynomial are not 0, and thereafter the division is executed. Also when the highest degree of the remainder polynomial during the division becomes 0, similarly, the division is executed after the coefficient data of the remainder polynomial are shifted until the highest degree of the remainder polynomial is not 0.) In a similar manner as Eq. 1, the division operation is repeated until the degree of the remainder of the dividend polynomial becomes smaller than that of the divisor polynomial.
The coefficient data of the resultant remainder polynomial (indicated by R'(Z)) are represented by Di(i=0, 1, 2, . . . , m-2). When the degree of R'(Z) fails to satisfy the conditions shown in FIG. 1, the division is repeated while setting R(Z) as the dividend polynomial, and R'(Z) as the divisor polynomial. In the divider circuit, the exchange of the divisor polynomial and the dividend polynomial is conducted by switching the selectors 82 and 83 in the same manner as the above. This operation is executed until the termination conditions of the Euclidean algorithm are satisfied.
FIG. 14 is a diagram illustrating the operation principle of the circuit for performing the division of polynomials over a Galois field in the prior art example. In FIG. 14, 90 designates registers for storing coefficient data of the dividend polynomial, 91 designates registers for storing coefficient data of the divisor polynomial, 92 designates a divider, 93 designates multipliers, 94 designates adders, and 95 designates an input terminal. The registers 90 and 91, the divider 92, the multipliers 93 and the adders 94 constitute the divider for polynomials over a Galois field. Since FIG. 14 illustrates only the operation of dividing polynomials over a Galois field, some means such as exchange means for the Euclidean algorithm are not shown. In order to simplify the illustration, the degree detection circuit is omitted.
Next, the operation of performing a division of polynomials over a Galois field in the divider having the shift register of FIG. 14 will be described. The description deals with a division of the following dividend and divisor polynomials in the configuration of the divider shown in FIG. 14: EQU Dividend polynomial: A(Z)=Z.sup.8 .revreaction.Z.sup.7 +Z.sup.5 +Z.sup.2 +1 EQU Divisor polynomial: B(Z)=Z.sup.6 +Z.sup.3 +Z.sup.2 +1
In this prior art example, the coefficients of the dividend polynomial A(Z) are set in the registers 90, and the coefficient data of the divisor polynomial B(Z) in the registers 91. The division of the polynomials over a Galois field is executed by performing the arithmetic while sequentially shifting the contents of the registers 90 to the right in which the coefficient data of the dividend polynomial A(Z) and which are arranged in the form of a shift register. FIG. 14 shows also the contents of the coefficient data stored in the registers in the case that the dividend polynomial A(Z) is divided by the divisor polynomial B(Z).
Initially, as shown in FIG. 14(a), the coefficients of the dividend polynomial A(Z) are set in the registers 90, and the coefficient data of the divisor polynomial B(Z) in the registers 91. In this prior art example, the highest-degree coefficient is set in the right end register. The numerals in the boxes representing the registers and shown in the figure indicate the coefficient data which are set in the respective registers. While the arithmetic is performed in the state shown in FIG. 14(a) on each coefficient in the divider 92, multipliers 93 and adders 94, the coefficients of the dividend polynomial are shifted one place to the right, with the result that the contents of the registers are changed as shown in FIG. 14(b). The divider 92 are constructed so that the highest-degree coefficient of the dividend polynomial side is divided by the highest-degree coefficient of the divisor polynomial side.
The state of each coefficient is represented by a numeral. That is, in the registers 90 for storing the coefficient data of the dividend polynomial, a remainder obtained by dividing the dividend polynomial by the divisor polynomial and reducing the degree of the dividend polynomial by one is automatically set. This remainder is used as the dividend polynomial in the next division. After the second division is conducted in the same manner, the remainder is set in the registers 90 as shown in FIG. 14(c). The result of the third division conducted in the same manner is shown in FIG. 14(d). This division operation is repeated until the degree of the dividend polynomial becomes smaller than that of the divisor polynomial. In this prior art example, since the difference between the degree of the dividend polynomial A(Z) and that of the divisor polynomial B(Z) is two, the division operation is repeated three times.
The above process will be ascertained by longhand calculation. The procedure of longhand calculation in which the division of the polynomials over a Galois field (the above-mentioned division of A(Z)/B(Z) is conducted is shown in Eq. 3 below. ##EQU6##
As seen from Eq. 3, the remainders of the division steps correspond to the states of FIGS. 14(a) to 14(d), respectively. In this case, the data stored in the registers 90 are the coefficient data of the remainder polynomial which is obtained by dividing the dividend polynomial by the divisor polynomial. Therefore, the employment of the divider in the form of a shift register as shown in FIG. 14 allows a division of polynomials over a Galois field to be performed for each polynomial.
Next, the operation of the divider section for the Euclidean arithmetic of the error-correcting apparatus for decoding a Reed-Solomon code in accordance with the Euclidean algorithm shown in FIG. 1 will be described with reference to FIG. 13. In the prior art example, a Reed-Solomon code having the minimum Hamming distance of 17 which is employed in an optical disk or the like is decoded. A syndrome polynomial S(Z) generated from a reproduced signal is expressed by EQU S(Z)=S.sub.15 Z.sup.15 +S.sub.14 Z.sup.14 +S.sub.13 Z.sup.13 +S.sub.i Z+S.sub.c
When the Euclidean arithmetic is started, in response to the Euclidean arithmetic start signal from the Euclidean arithmetic controller 89, the coefficients of the dividend polynomial Z.sup.2t (in this example, it is Z.sup.16 because the code has the minimum Hamming distance of 17) which is the initial value are stored in the registers 81a, and the coefficient data of the syndrome polynomial S(Z) which is the divisor polynomial are stored in the registers 81b. In the counters of the degree detection circuits 87 and 88, the values of 16 and 15 which are the initial values of the respective degrees are set, respectively. The degree detection circuits 87 and 88 are constructed so that their count values are decremented by one each time the contents of the registers 81a and 81b storing the coefficient data of the dividend polynomial are shifted.
In this prior art example, registers closer to the right end store the coefficient data of the highest degree. At the same time, the degree detection circuit 88 checks the syndrome polynomial which is the divisor polynomial to judge whether the coefficient data of the highest degree is 0 or not. When the coefficient data of the highest degree of the divisor polynomial (syndrome polynomial) detected in the degree detection circuit 88 is 0, the Euclidean arithmetic controller 89 controls the registers 81b storing the coefficient data of the divisor polynomial, so that the contents of the registers are shifted and this sifting operation is repeated until the data of the highest degree is not 0. In this case, the count value of the degree counter of the degree detection circuit 88 is decremented. When this operation is completed, the selectors 82 are controlled so as to select the outputs of the registers 81a, and the selectors 83 are controlled so as to select the outputs of the registers 81b.
The registers 81a which store the coefficient data of the dividend polynomial latch the output of the respective adder 86 when the clock signal is input. The registers 81b which store the coefficient data of the divisor polynomial retain the coefficient data. Although the specific control circuit is not shown in FIG. 13, the configuration for retaining the coefficient data of the divisor polynomial in the registers is realized by inhibiting the clock signals (clock 1 and clock 2) which are to be respectively supplied to the registers 81a and 81b, from being supplied to the registers which store the coefficient data of the divisor side. Alternatively, the configuration may be realized by connecting a selector before each of the registers 81a and 81b so that the selectors connected to the registers storing the coefficients of the dividend side select the outputs of the adders 86 and the registers storing the coefficients of the divisor side latch the outputs of themselves. The arithmetic circuits (the divider 84, the multipliers 85 and the adders 86) shown in the figure perform the arithmetic defined over a Galois field.
Hereinafter, referring to FIG. 15, the operation of the divider in the prior art Euclidean arithmetic circuit will be described. FIG. 15(a) shows the state where Z.sup.16 which is the initial value is set as the dividend polynomial in the registers 81a and the syndrome polynomial S(Z) is set as the divisor polynomial in the registers 81b. The numerals and symbols in the boxes representing the registers indicate the coefficient data stored in the respective registers. In order to simplify the description, it is assumed that, in this prior art example, the highest-degree coefficient of the syndrome polynomial is not 0, and that coefficient data of the highest degree of the polynomials stored in the registers are positioned at the right end. In this figure, for the sake of the illustration of the operation, the outputs of the registers 81a and 81b are directly connected to the divider 84, the multipliers 85 and the adders 86 which are selected by the selectors 82 and 83, respectively.
The divider of FIG. 15 has the same configuration as that of the divider of FIG. 14, and performs the division by repeating the shift operation until the degree of the remainder of the dividend polynomial becomes smaller than the degree of the divisor polynomial. The end of the division is determined by the Euclidean arithmetic controller 89 on the basis of information indicative of the degrees and output from the degree detection circuits 87 and 88. FIG. 15(b) shows the state of the coefficient data stored in the registers 81a and 81b at the completion of the division operation. In the figure, H.sub.14 to H.sub.0 stored in the registers 81a are the coefficient data of the remainder polynomial.
Then, when the conditions (in this example, the degree of the remainder polynomial is 7 or less) for terminating the Euclidean arithmetic are satisfied judging from information indicative of the degree of the remainder polynomial which is output from the degree detection circuit 87 (or 88), the Euclidean arithmetic controller 89 terminates the Euclidean arithmetic. When the termination conditions are not satisfied, the controller 89 performs the arithmetic while the polynomial which is the divisor polynomial in the previous arithmetic is set as the dividend polynomial. At this time, the divider section (core circuit) in the Euclidean arithmetic circuit of FIG. 13 judges whether the highest degree of the divisor polynomial (the remainder polynomial) is 0 or not. If 0, the contents of the registers 81a are shifted until the highest degree of the divisor polynomial (the remainder polynomial) is not 0, and control signals for switching the outputs of the selectors 82 and 83 are thereafter produced so that the selectors 82 select the outputs of the registers 81b and the selectors 83 select the outputs of the registers 81a.
This connecting state is shown in FIG. 15(c). As shown in the figure, the exchange of the dividend and divisor polynomials is executed by changing the connections to the arithmetic circuits by the selectors 82 and 83. (The configuration of the circuit is the same as that of the divider of FIG. 14.) In the same manner as the above-described example, the division is executed by repeating the shift operation while performing the arithmetic on the contents of the registers storing the coefficient data of the dividend polynomial, until the degree of the remainder of the dividend polynomial becomes smaller than the degree of the divisor polynomial. FIG. 15(d) shows the state of the coefficient data stored in the registers 81a and 81b at the completion of the division. In the figure, I.sub.13 to I.sub.0 stored in the registers 81b are the coefficient data of the remainder polynomial.
Then, the degree of the remainder polynomial is checked to judge whether or not the predetermined conditions are satisfied. If not, the connection states of the selectors 82 and 83 are changed, and the division operation in accordance with the Euclidean algorithm is conducted again. This division operation is repeated until the degree of the remainder polynomial is 7 or less. When a Reed-Solomon code is to be decoded, therefore, the division of polynomials over a Galois field in accordance with the Euclidean algorithm can be conducted for each polynomial, thereby improving the speed of the error-correcting process.
In order to accelerate the speed of the Euclidean arithmetic, the divider section (core circuit) for polynomials defined over a Galois field in the Euclidean arithmetic circuit of the prior art error-correcting apparatus is configured as described above. When the Euclidean arithmetic is to be performed, however, the outputs of the registers are connected to the selectors in order to exchange polynomials. In the case that a code having the minimum Hamming distance of 17 which is employed in an optical disk is to be decoded as described in the prior art example, therefore, selectors must be provided for each of the registers and the control of these selectors must be performed. This causes the circuit to be enlarged to a scale larger than needed, and further requires a selector control circuit for controlling the selectors, and a bus for control signals. In other words, the divider (core circuit) for polynomials defined over a Galois field in the Euclidean arithmetic process which circuit is disclosed in Japanese Patent Application Laid-Open No. HEI3-172,027 (1991) can perform the division of the polynomials, but has problems in that the circuit scale is unnecessarily enlarged and that the control is complicated.